#!/usr/bin/env python
# coding: utf-8

"""
Created on 25/10/2011

@author: Rubén López
@author: Alfredo Campuzano
"""

# TODO: refactor NFA and DFA into a superclass.
# TODO: refactor NFA.accepts() to avoid use os global variable.
# TODO: comment NFA.accepts() better.

import subprocess
import shlex

# Node shapes an colors
DOUB_CIRC_RED   = " [shape=doublecircle, style=filled, color=coral];\n"
DOUB_CIRC_BLACK = " [shape=doublecircle, color=black];\n"
CIRCLE_RED      = " [shape=circle, style=filled, color=coral];\n"
CIRCLE_BLACK    = " [shape=circle, color=black];\n"

#global variables
RES_DERIVATIONS = []

class NFA:
    """Representation of a Non-deterministic Finite Automata with only one
    final state.
    """

    def __init__(self, initial=0, final=0, states=[], alphabet=[]):
        self.initial = initial
        self.final = final
        self.states = states[::]
        self.alphabet = alphabet[::]
        if "ε" not in self.alphabet:
            self.alphabet.append("ε")
        self.transitions = []
        for state in self.states:
            aux = []
            for literal in self.alphabet:
                aux.append([])
            self.transitions.append(aux)
        self.current_state = None

    def add_transition(self, state0, state1, char):
        """Adds a transition from state0 to state1 on the input literal to
        this NFA.
        """

        if state0 not in self.states:
            self.add_state(state0)
        if state1 not in self.states:
            self.add_state(state1)
        i = self.states.index(state0)
        j = self.alphabet.index(char)
        k = self.states.index(state1)
        self.transitions[i][j].append(k)

    def add_state(self, state):
        """Adds a new state to this NFA."""

        if state not in self.states:
            self.states.append(state)
            aux = []
            for literal in self.alphabet:
                aux.append([])
            self.transitions.append(aux)

    def next_states(self, state0, char):
        """Returns a list whit the next states from state0 given the input
        character.
        """

        i = self.states.index(state0)
        j = self.alphabet.index(char)
        states = []
        for transition in self.transitions[i][j]:
            states.append(self.states[transition])
        return states

    def draw(self, filename=""):
        """Draw this nfa."""

        dot = self.dot()

        out = 'png/' + filename + '.png'

        with open(out, 'w') as outfile:
            subprocess.Popen(shlex.split('dot -Tpng'),
                stdin=subprocess.PIPE, stdout=outfile).communicate(dot)

    def accepts(self, input, filename=""):
        """Returns a tuple with: 1) the result value (True if the input text
        is accepted). 2) a list of tuples of the form (derivation,
        next_state). 3) A dictionary with the filenames of the images for
        each state (state -> filename)."""

        
        # Set initial values
        self.current_state = self.initial
        
        # list of tuples '(derivation, next_state)' (i.e.: ("0,'a'->1", 1))
        derivations = []
        
        # dict of form 'state->filename' (0 -> filename.0.png)
        images = {} 

        # If filename is not given, set a default filename
        if filename == "":
            filename = "nfa"

        # Draw image for the initial state of this nfa
        # Filenames for images are of the form 'filename.state.png'
        # where 'filename' is the given filename, 'state' is the current
        # state of this nfa, and '.png' is the extension for this
        # kind of files.
        image_filename = filename + "." + str(self.current_state)
        self.draw(image_filename)

        # First derivation
        derivations.append(('BEGIN -> 0', self.current_state))
        images[self.current_state] = image_filename

        if self.__accepts(input, 0, derivations, filename):
            result = True
        else:
            result = False

        # Return result (True or False), RES_DERIVATIONS (derivation, next state),
        # images (dict: state -> image)
        for derivation in RES_DERIVATIONS:
            if derivation[1] not in images.keys():
                image_filename = filename + "." + str(derivation[1])
                self.current_state = derivation[1]
                self.draw(image_filename)
                images[derivation[1]] = image_filename

        self.current_state = None

        return result, RES_DERIVATIONS, images

    def __accepts(self, input, pos, derivations, filename):
        """Test whether there is some path for the NFA to reach
        an accepting state from the current state, reading the
        given input at the given character position. """

        if (pos == len(input)):
            
            # Accepts if current state is a final state
            if self.current_state == self.final:
                while len(RES_DERIVATIONS) > 0:
                    RES_DERIVATIONS.pop()
                for derivation in derivations:
                    RES_DERIVATIONS.append(derivation)
                return True
            else:
                # Try to reach to a final state with empty string
                states = set()
                states.add(self.current_state)
                stack = [self.current_state]

                u = stack.pop()
                next_states = self.next_states(u, "ε")

                for s in self.next_states(u, "ε"):
                    if s not in states:
                        if s == self.final:
                            derivation = str(self.current_state) + \
                                ", '" + "ε" + "' -> " + str(s)
                            derivations.append((derivation, s))
                            while len(RES_DERIVATIONS) > 0:
                                RES_DERIVATIONS.pop()
                            for derivation in derivations:
                                RES_DERIVATIONS.append(derivation)
                            return True
                        stack.append(s)
                        states.add(s)

                while len(stack) > 0:
                    u = stack.pop()
                    derivation = str(self.current_state) + \
                        ", '" + "ε" + "' -> " + str(s)
                    derivations.append((derivation, u))
                    if u == self.final:
                        while len(RES_DERIVATIONS) > 0:
                            RES_DERIVATIONS.pop()
                        for derivation in derivations:
                            RES_DERIVATIONS.append(derivation)
                        return True
                    next_states = self.next_states(u, "ε")
                    if len(next_states) == 0:
                        derivations.pop()
                    for s in self.next_states(u, "ε"):
                        if s not in states:
                            stack.append(s)
                            states.add(s)

                while len(RES_DERIVATIONS) > 0:
                    RES_DERIVATIONS.pop()
                for derivation in derivations:
                    RES_DERIVATIONS.append(derivation)
                    
                return False

        # Get all next states with empty string
        next_states = self.next_states(self.current_state, "ε")

        # next_states is an array of 0 or more states, 
        # try each move recursively
        if len(next_states) > 0:
            for state in next_states:
                derivation = str(self.current_state) + \
                    ", '" + "ε" + "' -> " + str(state)
                derivations.append((derivation, state))
                self.current_state = state
                if self.__accepts(input, pos, derivations, filename):
                    return True
                else:
                    derivations.pop()

        char = input[pos]

        # Get all next states with the char at the current position of 
        # the input
        next_states = self.next_states(self.current_state, char)

        for state in next_states:
            derivation = str(self.current_state) + \
                ", '" + str(char) + "' -> " + str(state)
            derivations.append((derivation, state))
            self.current_state = state
            if self.__accepts(input, pos + 1, derivations, filename):
                return True
            else:
                derivations.pop()

        return False


    def dot(self):
        """Return a string in dot format that represents this dfa."""

        # Sort out states
        states = []
        states.extend(self.states)
        states.sort()
        
        # Begin dot
        dot = 'digraph dfa { \nrankdir=LR;\n'
        
        # Indicate initial state
        dot += 'BEGIN [shape = plaintext];\n'
        
        # Draw the node shapes
        for state in states:
            if state == self.final:
                if state == self.current_state:
                    dot += str(state) + DOUB_CIRC_RED
                else:
                    dot += str(state) + DOUB_CIRC_BLACK
            else:
                if state == self.current_state:
                    dot += str(state) + CIRCLE_RED
                else:
                    dot += str(state) + CIRCLE_BLACK
                    
        # Draw the edges
        dot += 'BEGIN -> ' + str(self.initial) + ';\n'
        for state0 in states:
            for char in self.alphabet:
                for state1 in self.next_states(state0, char):
                    dot += str(state0) + ' -> ' + str(state1) + \
                        ' [label = "' + str(char) + '"];\n'
                        
        # Finish dot
        dot += '}'

        return dot

    def __str__(self):

        states = []
        states.extend(self.states)
        states.sort()
        result = ""
        for state0 in states:
            for char in self.alphabet:
                for state1 in self.next_states(state0, char):
                    result += str(state0) + ", '" + str(char) + \
                    "' -> " + str(self.states[state1]) + "\n"
        return result

class DFA:
    """Representation of a Deterministic Finite Automata with only one
    final state.
    """

    def __init__(self, initial=0, final=[], states=[], alphabet=[]):
        self.initial = initial
        self.final = final
        self.states = states
        self.alphabet = alphabet[::]
        if "ε" in self.alphabet:
            self.alphabet.remove("ε")
        self.transitions = []
        for state in self.states:
            aux = []
            for literal in self.alphabet:
                aux.append(-1)
            self.transitions.append(aux)
        self.current_state = None

    def add_transition(self, state0, state1, char):
        """Adds a transition from state0 to state1 on the input char to
        this DFA.
        """

        if state0 not in self.states:
            self.add_state(state0)
        if state1 not in self.states:
            self.add_state(state1)
        i = self.states.index(state0)
        j = self.alphabet.index(char)
        k = self.states.index(state1)
        self.transitions[i][j] = k

    def add_state(self, state):
        """Adds a new state to this DFA."""

        if state not in self.states:
            self.states.append(state)
            aux = []
            for literal in self.alphabet:
                aux.append(-1)
            self.transitions.append(aux)

    def remove_state(self, state):
        """Remove a state from this DFA."""

        number = self.states.index(state)
        self.transitions.pop(number)
        self.states.remove(state)

        #Correct the transitions table
        for state in self.states:
            for literal in self.alphabet:
                i = self.states.index(state)
                j = self.alphabet.index(literal)
                if self.transitions[i][j] > number:
                    self.transitions[i][j] = self.transitions[i][j] - 1
                elif self.transitions[i][j] == number:
                    self.transitions[i][j] = -1

        #Correct the states numbers
        for state in self.states:
            if state > number:
                i = self.states.index(state)
                self.states[i] = i

    def next_state(self, state0, char):
        """Returns the next state from state0 given the input
        character."""

        i = self.states.index(state0)
        j = self.alphabet.index(char)
        state = self.states[self.transitions[i][j]]
        return state

    def draw(self, filename=""):
        """Draw this dfa."""

        dot = self.dot()

        out = 'png/' + filename + '.png'

        with open(out, 'w') as outfile:
            subprocess.Popen(shlex.split('dot -Tpng'),
                stdin=subprocess.PIPE, stdout=outfile).communicate(dot)

    def accepts(self, input, filename=""):
        """Returns a tuple with: 1) the result value (True if the input text
        is accepted). 2) a list of tuples of the form (derivation,
        next_state). 3) A dictionary with the filenames of the images for
        each state (state -> filename)."""

        # Set initial values
        self.current_state = self.initial
        
        # list of tuples '(derivation, next_state)' (i.e.: ("0,'a'->1", 1))
        derivations = []
        
        # dict of form 'state->filename' (0 -> filename.0.png)
        images = {} 

        # If filename is not given, set a default filename
        if filename == "":
            filename = "dfa"

        # Draw image for the initial state of this dfa
        # Filenames for images are of the form 'filename.state.png'
        # where 'filename' is the given filename, 'state' is the current
        # state of this dfa, and '.png' is the extension for this
        # kind of files.
        image_filename = filename + "." + str(self.current_state)
        self.draw(image_filename)

        # First derivation
        derivations.append(('BEGIN -> 0', self.current_state))
        images[self.current_state] = image_filename

        for char in input:

            if char not in self.alphabet:
                return False, derivations, images

            next_state = self.next_state(self.current_state, char)

            # Return if there is no next state (if state number is -1)
            if not next_state >= 0:
                derivation = str(self.current_state) + \
                    ", '" + str(char) + "' -> "
                derivations.append((derivation, next_state))
                return False, derivations, images

            # Append the derivation to the derivations list and the
            # data asociated with it.
            derivation = str(self.current_state) + ", '" + \
                str(char) + "' -> " + str(next_state)
            derivations.append((derivation, next_state))

            # Move to next state
            self.current_state = next_state

            # If there is no image for this state, draw the image
            # and save the filename in the images dict. This is
            # useful to avoid drawing one image for each derivation
            if self.current_state not in images.keys():
                image_filename = filename + "." + str(self.current_state)
                self.draw(image_filename)
                images[self.current_state] = image_filename

        result = self.current_state in self.final
        self.current_state = None

        # Return result (True or False), derivations (derivation, next state),
        # images (dict: state -> image)
        return result, derivations, images

    def dot(self):
        """Retur a string in dot format that represents this dfa."""

        # Sort out states
        states = []
        states.extend(self.states)
        states.sort()
        
        # Begin dot
        dot = 'digraph dfa { \nrankdir=LR;\n'
        
        # Indicate initial state
        dot += 'BEGIN [shape = plaintext];\n'
        
        # Draw the node shapes
        for state in states:
            if state in self.final:
                if state == self.current_state:
                    dot += str(state) + DOUB_CIRC_RED
                else:
                    dot += str(state) + DOUB_CIRC_BLACK
            else:
                if state == self.current_state:
                    dot += str(state) + CIRCLE_RED
                else:
                    dot += str(state) + CIRCLE_BLACK
                    
        # Draw the edges
        dot += 'BEGIN -> ' + str(self.initial) + ';\n'
        for state0 in states:
            for char in self.alphabet:
                state1 = self.next_state(state0, char)
                if state1 >= 0:
                    dot += str(state0) + ' -> ' + str(state1) + \
                              ' [label = "' + str(char) + '"];\n'
                              
        # Finish dot
        dot += '}'

        return dot

    def __str__(self):

        states = []
        states.extend(self.states)
        states.sort()
        result = ""
        for state0 in states:
            for char in self.alphabet:
                state1 = self.next_state(state0, char)
                if state1 >= 0:
                    result += str(state0) + ", '" + str(char) + \
                    "' -> " + str(state1) + "\n"
        return result
